Entropy Pool
% Remco Bloemen % 2015-08-26
Random number generation is an underestimate challenge in any cryptographic system. You need it for generating keys and nonces, and often the security of the entire system depends on it.
For example, Blockchain.info’s late 2014 security breach is caused by using non-random nonces. Even though the breach was fixed in two and a half hours, it still led to the bitcoins of hunderds of addresses being stolen. Similarly a lot of Mobile wallets got robbed and the Sony Playstation 3 root key got stolen because non-random nonces.
Whenever possible, it’s best to avoid using random numbers altogether. For example in the digital signature algorithm, instead of using a random nonce, you can use a hash of the message. This won’t loose you any security and has been promoted by RFC 6979. If Blockchain and Sony had implemented this recommendation, there would have never been a breach.
Overall design
- Entropy sources: These are streams of bits that.
- Entropy accumulator
Entropy sources
Some program accessible sources of entropy are:
rdrand
instruction- Screen capture
- High resolution clocks
- Wall-time clocks
- Stored entropy
- IO input and timings
- Operating system entropy sources
- Standard library entropy sources
- Microphone / webcam input (Just don’t point your your webcam at a lavalamp or you will need to license US 5732138 from SGI.)
- Hardware random number generators (if available)
- Processor internal state (HAVEGE)
So we have a lot of sources that can provide us with a tiny bit of security. We would like to combine those into one source that can provide us with a lot of security. We don’t want to design a system like a chain, where if one link breaks, the load falls. We want to design the system like braided rope, all strands need to break before the load is lost.
Luckily, for random number generators we can create the braided rope.
Pseudo random number generators
void seed(const Bytes bytes); Bytes extract(uint length);
Entropy accumulator
How to Eat Your Entropy and Have it Too Optimal Recovery Strategies for Compromised RNGs http://eprint.iacr.org/2014/167.pdf Random number generators (RNGs) play a crucial role in many cryptographic schemes and protocols, but their security proof usually assumes that their internal state is initialized with truly random seeds and remains secret at all times. However, in many practical situations these are unrealistic assumptions: …